package com.lry.basic.algorithm.common;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/8/27
 */
public class ThreeNumberSum {
    public static void main(String[] args) {
        System.out.println(threeNumberSum(new int[]{-1,-1,2,1,-2,-1,1}));
    }

    public static List<List<Integer>> threeNumberSum(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        if(nums==null||nums.length<3)return result;
        Arrays.sort(nums);
        for(int p=0;p<nums.length;){
            if(nums[p]>0)break;
            int i = p+1;
            int j = nums.length-1;
            while(i<j){
                int sum = nums[p]+nums[i]+nums[j];
                if(sum==0){//i向后移动，j向前移动
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[p]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    result.add(list);
                    int tmp = nums[i];
                    while(i<nums.length&&tmp==nums[i]){
                        i++;
                    }
                    tmp = nums[j];
                    while(i<nums.length&&tmp==nums[j]){
                        j--;
                    }
                }else if(sum>0){//j向前移
                    int tmp = nums[j];
                    while(i<nums.length&&tmp==nums[j]){
                        j--;
                    }
                }else{//i向后移
                    int tmp = nums[i];
                    while(i<nums.length&&tmp==nums[i]){
                        i++;
                    }
                }
            }

            int tmp = nums[p];
            while(p<nums.length&&tmp==nums[p]){
                p++;
            }
        }
        return result;
    }
}
